﻿#pragma once
namespace Aurora
{
	//颜色
	enum Color
	{
		RED,
		BLACK
	};
	//红黑树节点
	template<class K,class V>
	struct RBTreeNode
	{
		std::pair<K, V> _kv;
		RBTreeNode<K,V>* _left;
		RBTreeNode<K,V>* _right;
		RBTreeNode<K,V>* _parent;
		Color _col;
		RBTreeNode(const std::pair<K,V>& kv)
			:_kv(kv)
			,_left(nullptr)
			,_right(nullptr)
			,_parent(nullptr)
			,_col(BLACK)
		{}
	};
	template<class K,class V>
	class RBTree
	{
		using Node = RBTreeNode<K,V>;
	public:
		//默认构造
		RBTree():_root(nullptr)//,_size(0)
		{}
		//插入
		bool insert(const std::pair<K,V>& kv)
		{
			//判断该树是否为空
			if (_root == nullptr)
			{
				_root = new Node(kv);
				_root->_col = BLACK;
				//_size++;
				return true;
			}
			//该树不为空的话就寻找位置
			Node* cur = _root;
			Node* parent = nullptr;
			while (cur)
			{
				if (cur->_kv.first > kv.first)
				{
					parent = cur;
					cur = cur->_left;
				}
				else if (cur->_kv.first < kv.first)
				{
					parent = cur;
					cur = cur->_right;
				}
				else return false;
			}
			//申请新节点
			cur = new Node(kv);
			//插入红色节点,可能会调整,但是插入黑色节点,必定会错
			cur->_col = RED;
			//判断插入哪边
			if (parent->_kv.first > kv.first)
			{
				parent->_left = cur;
			}
			else if (parent->_kv.first < kv.first)
			{
				parent->_right = cur;
			}
			//修改cur节点的_parent指针的指向
			cur->_parent = parent;
			//调整
			while (parent && parent->_col == RED)
			{
				//计算爷爷节点
				Node* grandpa = parent->_parent;
				//判断parent在grandpa的哪边
				if (parent == grandpa->_left)
				{
					//计算叔叔节点
					Node* uncle = grandpa->_right;
					//叔叔存在且为红
					if (uncle && uncle->_col == RED)
					{
						//单纯的变色
						uncle->_col = parent->_col = BLACK;
						grandpa->_col = RED;
						//继续往上更新
						cur = grandpa;
						parent = cur->_parent;
					}
					else//叔叔不存在或者叔叔存在且为黑
					{
						if (cur == parent->_left)
						{
							//    g
							//  p    u
							//c
							//右旋转
							RotateR(grandpa);
							parent->_col = BLACK;
							grandpa->_col = RED;
						}
						else if(cur == parent->_right)
						{
							//    g
							// p     u
							//    c
							//先左旋,再右旋
							RotateL(parent);
							RotateR(grandpa);
							cur->_col = BLACK;
							grandpa->_col = RED;
						}
						break;
					}
				}
				//parent在grandpa的右边,那么uncl就在左边
				else if (parent == grandpa->_right)
				{
					//计算uncle节点
					Node* uncle = grandpa->_left;
					//uncle存在且为红
					if (uncle && uncle->_col == RED)
					{
						//单纯的变色
						parent->_col = uncle->_col = BLACK;
						grandpa->_col = RED;
						//继续往上更新
						cur = grandpa;
						parent = cur->_parent;
					}
					else//叔叔存在且为黑或者叔叔不存在
					{
						if (cur == parent->_right)
						{
							//    g
							// u     p
							//          c
							//左旋转
							RotateL(grandpa);
							parent->_col = BLACK;
							grandpa->_col = RED;
						}
						else if(cur == parent->_left)
						{
							//    g
							// u      p
							//     c
							//先右旋,再左旋
							RotateR(parent);
							RotateL(grandpa);
							cur->_col = BLACK;
							grandpa->_col = RED;
						}
					}
				}
			}
			_root->_col = BLACK;
			//_size++;
			return true;
		}
		//中序遍历
		void InOrder()
		{
			_InOrder(_root);
		}
		//判断是否为红黑树
		bool IsRBTree()
		{
			if (_root == nullptr) return true;
			if (_root->_col == RED) return false;
			//计算最左侧黑色节点个数
			Node* cur = _root;
			size_t BlackNum = 0;
			while (cur)
			{
				if (cur->_col == BLACK)
					BlackNum++;
				cur = cur->_left;
			}
			return Check(_root, 0, BlackNum);
		}
		//高度
		size_t Hight()
		{
			return _Hight(_root);
		}
		//查找
		Node* Find(const K& key)
		{
			Node* cur = _root;
			while (cur)
			{
				if (cur->_kv.first > key)
				{
					cur = cur->_left;
				}
				else if (cur->_kv.first < key)
				{
					cur = cur->_right;
				}
				else if (cur->_kv.first == key)
				{
					return cur;
				}
			}
			return nullptr;
		}
		//size
		size_t size()
		{
			//return _size;
			return _size(_root);
		}
	protected:
		//右旋
		void RotateR(Node* parent)
		{
			//计算出要操作的节点
			Node* subL = parent->_left;
			Node* subLR = subL->_right;
			//保存parent的_parent节点
			Node* pphead = parent->_parent;
			//调整
			parent->_left = subLR;
			subL->_right = parent;
			//修改_parent指针
			parent->_parent = subL;
			if (subLR)
				subLR->_parent = parent;
			//调整pphead节点
			if (pphead == nullptr)
			{
				_root = subL;
				subL->_parent = nullptr;
			}
			else
			{
				if (pphead->_left = parent)
				{
					pphead->_left = subL;
				}
				else if (pphead->_right = parent)
				{
					pphead->_right = subL;
				}
				subL->_parent = pphead;
			}
		}
		//左旋
		void RotateL(Node* parent)
		{
			//保存需要调整的节点
			Node* subR = parent->_right;
			Node* subRL = subR->_left;
			//保存parent的_parent的节点
			Node* pphead = parent->_parent;
			//调整
			parent->_right = subRL;
			subR->_left = parent;
			//调整_parent
			parent->_parent = subR;
			if (subRL)
				subRL->_parent = parent;
			//调整pphead节点
			if (pphead == nullptr)
			{
				_root = subR;
				subR->_parent = nullptr;
			}
			else
			{
				if (pphead->_left == parent)
				{
					pphead->_left = subR;
				}
				else if(pphead->_right == parent )
				{
					pphead->_right = subR;
				}
				subR->_parent = pphead;
			}
		}
		//中序遍历
		void _InOrder(Node* root)
		{
			if (root == nullptr) return;
			_InOrder(root->_left);
			std::cout << root->_kv.first << ":" << root->_kv.second << std::endl;
			_InOrder(root->_right);
		}
		//检查是否为红黑树
		bool Check(Node* root, size_t BlackCount, size_t BlackNum)
		{
			if (root == nullptr)
			{
				if (BlackCount != BlackNum)
				{
					std::cout << "有两条路径的黑色节点数量不一样" << std::endl;
					return false;
				}
				return true;
			}
			if (root->_col == RED && root->_parent->_col == RED)
			{
				std::cout << "出现连续的红色节点" << std::endl;
				return false;
			}
			if (root->_col == BLACK)
			{
				BlackCount++;
			}
			return Check(root->_left, BlackCount, BlackNum) && Check(root->_right, BlackCount, BlackNum);
		}
		size_t _Hight(Node* root)
		{
			if (root == nullptr) return 0;
			size_t LeftHight = _Hight(root->_left);
			size_t RightHight = _Hight(root->_right);
			return LeftHight > RightHight ? LeftHight + 1 : RightHight + 1;
		}
		size_t _size(Node* root)
		{
			if (root == nullptr) return 0;
			return _size(root->_left) + _size(root->_right) + 1;
		}
	private:
		Node* _root;
		//size_t _size;
	};
}
